using System;
using System.Collections.Generic;

namespace OpenRay
{
	public class OctTreeScene : IScene
	{
		private readonly BoundingBox bounds;
		
		private OctTreeScene[] children = new OctTreeScene[8];
		private List<Primitive> primitives;
		
		private readonly int depth, maxPrimitives;
		
		public OctTreeScene (BoundingBox b, int d, int mp)
		{
			primitives = new List<Primitive>(mp);
			depth = d;
			maxPrimitives = mp;
			bounds = b;
		}
		
		public void AddPrimitive(Primitive p)
		{
			if ( p.BoundingBox().Overlaps( bounds ) ) {
				if ( primitives != null && primitives.Count < maxPrimitives ) {
					primitives.Add(p);	
				} else {
					if ( primitives != null && primitives.Count == maxPrimitives ) {
						IList<BoundingBox> childBounds = bounds.Octants();
						
						for( int i = 0; i < 8; i++ ) {
							children[i] = new OctTreeScene(childBounds[i], depth - 1, maxPrimitives);
						
							for ( int j = 0; j < primitives.Count; j++ )
								children[i].AddPrimitive(primitives[j]); 
						}
						
						primitives = null;
					}
					
					for( int i = 0; i < 8; i++ )
					{
						children[i].AddPrimitive( p );
					}
				}
			}
		}
		
		public IList<PrimitiveHit> Trace(Ray r, uint depth)
		{
			List<PrimitiveHit> ret = new List<PrimitiveHit>();
			
			if ( depth == 0 )
				return ret;
			
			if ( primitives == null ) {
				for ( int i = 0; i < 8; i++ ) {
					if ( children[i].bounds.Intersects(r) )
						ret.AddRange( children[i].Trace(r, depth) );
				}
			} else {
				for ( int i = 0; i < primitives.Count; i++ )
					primitives[i].Trace(r, depth, ret);
			}

			ret.Sort();
			
			return ret;
		}
	}
}

